package divideAndConquer;

/**
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可
 * @author le
 */
public class SearchForMinNumber
{
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        sort(arr,0,arr.length-1);
        for (int i = 0;i < k;i++){
            res[i] = arr[i];
        }
        return res;
    }

    public void sort(int[] arr, int left, int right){
        if (left < right){
            int key = arr[left];

            int i = left;
            int j = right;

            while(i < j){
                while(i < j && arr[j] > key){
                    j--;
                }
                if (i < j){
                    arr[i++] = arr[j];
                }
                while(i < j && arr[i] < key){
                    i++;
                }
                if (i < j){
                    arr[j--] = arr[i];
                }
            }
            arr[i] = key;
            sort(arr,left,i-1);
            sort(arr,i+1,right);
        }
    }

}
